package com.hle.graph;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
import java.util.Map.Entry;

import com.hle.MinHeap;
import com.hle.UnionFind;

@SuppressWarnings({"unchecked"})
public class ListGraph<V, E> extends Graph<V, E> {	
	private Map<V, Vertex<V, E>> verteices = new HashMap<>();  
	private Set<Edge<V, E>> edges = new HashSet<>();	

	public ListGraph() {}
	public ListGraph(WeightManager<E> weightManager) {
		super(weightManager);
	}

	private Comparator<Edge<V, E>> edgeComparator = (Edge<V, E> e1, Edge<V, E> e2) -> {
		return weightManager.compare(e1.weight, e2.weight);
	};

	public void print() {
		System.out.println("顶点--------------------");
		verteices.forEach((V v, Vertex<V, E> vertex) -> {
			System.out.println(v);
			System.out.println("-------- in edges");
			System.out.println(vertex.inEdges);
			System.out.println("-------- out edges");
			System.out.println(vertex.outEdges);
		});
		System.out.println("边--------------------");
		edges.forEach((Edge<V, E> edge) -> {
			System.out.println(edge);
		});
	}

	@Override
	public int edgesSize() {
		return edges.size();
	}

	@Override
	public int verticesSize() {
		return verteices.size();
	}

	@Override
	public void addVerTex(V v) {
		if (verteices.containsKey(v)) return;
		Vertex<V, E> verTex = new Vertex<>(v);
		verteices.put(v, verTex);
	}

	@Override
	public void addEdge(V from, V to) {
		addEdge(from, to, null);
	}

	@Override
	public void addEdge(V from, V to, E weight) {
		Vertex<V, E> fromVertex = verteices.get(from);
		Vertex<V, E> toVertex = verteices.get(to);
		if (fromVertex == null) {
			fromVertex = new Vertex<>(from);
			verteices.put(from, fromVertex);
		}
		if (toVertex == null)  {
			toVertex  = new Vertex<>(to);
			verteices.put(to, toVertex);
		}

		Edge<V, E> newEdge = new Edge<>(fromVertex, toVertex);
		newEdge.weight = weight;
		if (fromVertex.outEdges.remove(newEdge)) {
			toVertex.inEdges.remove(newEdge);
			edges.remove(newEdge);
		}
		fromVertex.outEdges.add(newEdge);
		toVertex.inEdges.add(newEdge);
		edges.add(newEdge);
	}

	@Override
	public void removeVerTex(V v) {
		Vertex<V, E> vertex = verteices.remove(v);
		if (vertex == null) return;

		for (Iterator<Edge<V, E>> iterator = vertex.outEdges.iterator(); iterator.hasNext();) {
			Edge<V, E> edge = iterator.next();		
			edge.to.inEdges.remove(edge);
			iterator.remove();
			edges.remove(edge);
		}

		for (Iterator<Edge<V, E>> iterator = vertex.inEdges.iterator(); iterator.hasNext();) {
			Edge<V, E> edge = iterator.next();		
			edge.from.outEdges.remove(edge);
			iterator.remove();
			edges.remove(edge);
		}

	}

	@Override
	public void removeEdge(V from, V to) {
		Vertex<V, E> fromVertex = verteices.get(from);
		if (fromVertex == null) return;

		Vertex<V, E> toVertex = verteices.get(to);
		if (toVertex == null) return;

		Edge<V, E> newEdge = new Edge<>(fromVertex, toVertex);
		if (fromVertex.outEdges.remove(newEdge)) {
			toVertex.inEdges.remove(newEdge);
			edges.remove(newEdge);
		}
	}

	private static class Vertex<V,E> {
		V value;
		/// 以他为终点的边 in 进来的
		Set<Edge<V,E>> inEdges = new HashSet<>();
		/// 以他为起点的边 out 出来的
		Set<Edge<V,E>> outEdges = new HashSet<>();
		public Vertex(V value) {
			this.value = value;
		}

		@Override
		public String toString() {
			return value.toString();
		}

		@Override
		public boolean equals(Object obj) {
			Vertex<V, E> tmpVertex = (Vertex<V, E>)obj;
			return Objects.equals(tmpVertex.value, value);
		}

		@Override
		public int hashCode() {
			// TODO Auto-generated method stub
			return value.hashCode();
		}
	}

	private static class Edge<V,E> {
		Vertex<V,E> from;
		Vertex<V,E> to;
		E weight;
		public Edge(Vertex<V, E> from, Vertex<V, E> to) {
			this.from = from;
			this.to = to;
		}

		@Override
		public boolean equals(Object obj) {
			Edge<V, E> tmpObj = (Edge<V, E>)obj;
			return Objects.equals(from, tmpObj.from) && Objects.equals(to, tmpObj.to);
		}
		@Override
		public int hashCode() {
			return from.hashCode() * 31 +  to.hashCode();
		}

		@Override
		public String toString() {
			return "Edge [from=" + from + ", to=" + to + ", weight=" + weight + "]";
		}	

		public EdgeInfo<V, E> info() {
			return new EdgeInfo<>(from.value, to.value, weight);
		}
	}

	@Override
	public void bfs(V begin, VertexVisitor<V> visitor) {
		if (visitor == null) return;
		Vertex<V, E> beginVertex = verteices.get(begin);
		if (beginVertex == null) return;

		Set<Vertex<V, E>> visitedVerteices = new HashSet<>();
		Queue<Vertex<V, E>> queue = new LinkedList<>();
		queue.offer(beginVertex);
		visitedVerteices.add(beginVertex);
		while(!queue.isEmpty()) {
			Vertex<V, E> vertex = queue.poll();
			if (visitor.visit(vertex.value)) break;
			vertex.outEdges.forEach((Edge<V,E> edge)->{
				if(!visitedVerteices.contains(edge.to)) {
					queue.offer(edge.to);
					visitedVerteices.add(edge.to);
				}
			});
		}
	}

	@Override
	public void dfs(V begin, VertexVisitor<V> visitor) {
		if (visitor == null) return;
		Vertex<V, E> vertex = verteices.get(begin);
		if (vertex == null) return;
		Set<Vertex<V, E>> visitedVerteices = new HashSet<>();
		dfs(vertex,visitedVerteices,visitor);
	}

	private void dfs(Vertex<V, E> vertex,Set<Vertex<V, E>> set,VertexVisitor<V> visitor) {
		if (visitor.visit(vertex.value)) return;
		set.add(vertex);
		for (Edge<V, E> edge : vertex.outEdges) {
			if (set.contains(edge.to)) continue;
			dfs(edge.to,set,visitor);
		}
	}

	@Override
	public void dfs1(V begin, VertexVisitor<V> visitor) {
		if (visitor == null) return;
		Vertex<V, E> beginvertex = verteices.get(begin);
		if (beginvertex == null) return;
		Set<Vertex<V, E>> visitedVerteices = new HashSet<>();
		Stack<Vertex<V, E>> stack = new Stack<>();
		stack.push(beginvertex);
		visitedVerteices.add(beginvertex);
		if (visitor.visit(beginvertex.value)) return;
		while (!stack.isEmpty()) {
			Vertex<V, E> vertex =  stack.pop();
			for (Edge<V, E> edge : vertex.outEdges) {
				if (visitedVerteices.contains(edge.to)) continue;
				stack.push(edge.from);
				stack.push(edge.to);
				visitedVerteices.add(edge.to);
				if (visitor.visit(edge.to.value)) return;
				break;
			}
		}
	}

	@Override
	public List<V> topologicalSort() {
		List<V> list = new ArrayList<>();
		Queue<Vertex<V, E>> queue = new LinkedList<>();
		Map<Vertex<V, E>, Integer> hashMap = new HashMap<>();
		verteices.forEach((V v , Vertex vertex) -> {
			if (vertex.inEdges.size() == 0) {
				queue.offer(vertex);
			}else {
				hashMap.put(vertex, vertex.inEdges.size());
			}
		});

		while (!queue.isEmpty()) {
			Vertex<V, E> vertex = queue.poll();
			list.add(vertex.value);
			vertex.outEdges.forEach((Edge<V, E> edge) -> {
				int size = hashMap.get(edge.to) - 1;
				if (size == 0) {
					queue.offer(edge.to);
				}else {
					hashMap.put(edge.to, size);
				}
			});
		}
		return list;
	}

	@Override
	public Set<EdgeInfo<V, E>> mst() {
		return Math.random() > 0.5 ? prim() : kruskal();
	}

	private Set<EdgeInfo<V, E>> prim() {
		Set<EdgeInfo<V, E>> set = new HashSet<>();
		Set<Vertex<V, E>> addedVertices = new HashSet<>();
		Iterator<Vertex<V, E>> iterator = verteices.values().iterator();
		if (!iterator.hasNext()) return null;
		Vertex<V, E> vertex = iterator.next();
		MinHeap<Edge<V, E>> heap = new MinHeap<>(vertex.outEdges,edgeComparator);
		addedVertices.add(vertex);
		while (!heap.isEmpty()) {
			Edge<V, E> minEdge = heap.remove();
			if (addedVertices.contains(minEdge.to)) continue;
			set.add(minEdge.info());
			addedVertices.add(minEdge.to);
			heap.addAll(minEdge.to.outEdges);
		}
		return set;
	}

	private Set<EdgeInfo<V, E>> kruskal() {
		Set<EdgeInfo<V, E>> set = new HashSet<>();
		MinHeap<Edge<V, E>> heap = new MinHeap<>(edges, edgeComparator);
		UnionFind<Vertex<V, E>> union = new UnionFind<>();
		verteices.forEach((V v, Vertex<V,E> vertex) -> {
			union.makeSet(vertex);
		});
		while (!heap.isEmpty()) {
			Edge<V, E> edge = heap.remove();
			if(union.isSame(edge.from, edge.to)) continue;
			set.add(edge.info());
			union.union(edge.from, edge.to);
		}
		return set;
	}

	private Entry<Vertex<V, E>, PathInfo<V, E>> getMinPath(Map<Vertex<V, E>,PathInfo<V, E>> paths) {
		Iterator<Map.Entry<Vertex<V, E>, PathInfo<V, E>>> it =  paths.entrySet().iterator();
		Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = it.next(); 
		while (it.hasNext()) {
			Entry<Vertex<V, E>, PathInfo<V, E>> entry = it.next(); 
			if (weightManager.compare(entry.getValue().weight, minEntry.getValue().weight) < 0) {
				minEntry  =  entry;
			}
		}
		return minEntry;
	}
	
	
	@Override
	public Map<V, PathInfo<V, E>> shortestPath(V begin) {
//		return dijkstra(begin); 
		return bellmanFord(begin);
	}
	
	private Map<V, PathInfo<V, E>> bellmanFord(V begin) {
		Vertex<V, E> beginVertex = verteices.get(begin);
		if (beginVertex == null) return null;
		
		Map<V, PathInfo<V, E>> selectedPath = new HashMap<>();
		
		PathInfo<V, E> info = new PathInfo<>();
		info.weight = weightManager.zero();
		selectedPath.put(begin, info);
		
		int count = verticesSize() - 1;
		for (int i = 0; i < count; i++) {
			for (Edge<V, E> edge : edges) {
				PathInfo<V, E> pathInfo = selectedPath.get(edge.from.value);
				if (pathInfo == null) continue;
				relaxForBellmanFord(selectedPath, edge, pathInfo);
			}
		}
		selectedPath.remove(begin);
		return  selectedPath;
	}
	
	private Map<V, PathInfo<V, E>> dijkstra(V begin) {
		Vertex<V, E> beginVertex = verteices.get(begin);
		if (beginVertex == null) return null;

		Map<V, PathInfo<V, E>> selectedPath = new HashMap<>();
		Map<Vertex<V, E>, PathInfo<V, E>> paths = new HashMap<>();
		for (Edge<V, E> edge : beginVertex.outEdges) {
			PathInfo<V, E> pathInfo = new PathInfo<>();
			pathInfo.weight = edge.weight;
			pathInfo.paths.add(edge.info());
			paths.put(edge.to, pathInfo);
		}

		while (!paths.isEmpty()) {
			Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = getMinPath(paths);
			Vertex<V, E> minVertex = minEntry.getKey();
			selectedPath.put(minVertex.value, minEntry.getValue());
			paths.remove(minVertex);			
			for (Edge<V, E> edge : minVertex.outEdges) {
				if(selectedPath.containsKey(edge.to.value)) continue;
				relax(paths, edge, minEntry.getValue());
			}
		}
		selectedPath.remove(beginVertex.value);
		return selectedPath;
	}
	
	private void relax(Map<Vertex<V, E>, PathInfo<V, E>> paths, Edge<V, E> edge, PathInfo<V, E> fromPathInfo) {
		E newWeight = weightManager.add(fromPathInfo.weight, edge.weight);
		PathInfo<V, E> oldInfo = paths.get(edge.to);
		if (oldInfo == null || weightManager.compare(newWeight, oldInfo.weight) < 0) {
			PathInfo<V, E> info = new PathInfo<>();
			info.weight  = newWeight;
			info.paths.addAll(fromPathInfo.paths);
			info.paths.add(edge.info());
			paths.put(edge.to, info);
		}
	}
	
	private void relaxForBellmanFord(Map<V, PathInfo<V, E>> paths, Edge<V, E> edge, PathInfo<V, E> fromPathInfo) {
		E newWeight = weightManager.add(fromPathInfo.weight, edge.weight);
		PathInfo<V, E> oldInfo = paths.get(edge.to.value);
		if (oldInfo == null || weightManager.compare(newWeight, oldInfo.weight) < 0) {
			PathInfo<V, E> info = new PathInfo<>();
			info.weight  = newWeight;
			info.paths.addAll(fromPathInfo.paths);
			info.paths.add(edge.info());
			paths.put(edge.to.value, info);
		}
	}
	
	@Override
	public Map<V, Map<V, PathInfo<V, E>>> multShortestPath() {
		Map<V, Map<V, PathInfo<V, E>>> paths = new HashMap<>();
		for (Edge<V, E> edge : edges) {
			Map<V, PathInfo<V, E>> map = paths.get(edge.from.value);
			if (map == null) {
				map = new HashMap<>();
				paths.put(edge.from.value, map);
			}
			PathInfo<V, E> pathInfo = new PathInfo<>();
			pathInfo.weight = edge.weight;
			pathInfo.paths.add(edge.info());
			map.put(edge.to.value, pathInfo);
		} 
		
		verteices.forEach((V v2, Vertex<V, E> vertex2) -> {
			verteices.forEach((V v1, Vertex<V, E> vertex1) -> {
				verteices.forEach((V v3, Vertex<V, E> vertex3) -> {
					if (v2.equals(v1) || v1.equals(v3) || v2.equals(v3)) return;
					// v1 -> v2 
					PathInfo<V, E> pathInfo12 = paths.get(v1).get(v2);
					if (pathInfo12 == null) return;
					// v2 -> v3 
					PathInfo<V, E> pathInfo23 = paths.get(v2).get(v3);
					if (pathInfo23 == null) return;
					// v1 -> v3 
					PathInfo<V, E> pathInfo13 = paths.get(v1).get(v3);
					E newWeight = weightManager.add(pathInfo12.weight, pathInfo23.weight); 
					if (pathInfo13 != null && weightManager.compare(newWeight, pathInfo13.weight) >= 0) return;
					if (pathInfo13 == null) {
						pathInfo13 = new PathInfo<>();
						paths.get(v1).put(v3, pathInfo13);
					}else {
						pathInfo13.paths.clear();
					}
					pathInfo13.weight = newWeight;
					pathInfo13.paths.addAll(pathInfo12.paths);
					pathInfo13.paths.addAll(pathInfo23.paths);
				});
			});
		});
		return paths;
	}
}
